package com.zhugang.week09;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program algorithms
 * @description: pondSizes
 * @author: chanzhugang
 * @create: 2022/08/23 15:11
 */
public class PondSizes {

    /**
     * 面试题 16.19 水域大小
     * 连通性
     *
     * @param land
     * @return
     */
    private int count;
    private int n;
    private int m;

    public int[] pondSizes(int[][] land) {
        // 多个水域连接成池塘， 求池塘的大小（水域的个数）从小到大排序
        // 图上的DFS
        n = land.length;
        m = land[0].length;
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (land[i][j] == 0) {
                    // 水域
                    count = 0;
                    dfs(land, i, j);
                    result.add(count);
                }
            }
        }
        // list to array and sort
        int[] resultArray = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            resultArray[i] = result.get(i);
        }
        Arrays.sort(resultArray);
        return resultArray;
    }

    private void dfs(int[][] land, int curi, int curj) {
        count++;
        // 把水域改为不是0的就可以
        land[curi][curj] = 1;
        // 垂直、水平、对角线
        int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}, {-1, -1}, {1, 1}, {-1, 1}, {1, -1}};
        for (int d = 0; d < 8; d++) {
            int newi = curi + dirs[d][0];
            int newj = curj + dirs[d][1];
            if (newi >= 0 && newi < n && newj >= 0 && newj < m && land[newi][newj] == 0) {
                dfs(land, newi, newj);
            }
        }
    }
}